#define _CRT_SECURE_NO_WARNINGS 1;
#include "stdio.h"
#include <stdlib.h>

 struct ListNode {
      int val;
      struct ListNode *next;
  };

 ListNode* bunode(int x)
 {
     ListNode* ps = (ListNode*)malloc(sizeof(int));
     ps->val = x;
     ps->next = NULL;
     return ps;
 }

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* plist, * ptail;
    plist = NULL;
    ptail = NULL;

    ListNode* l1 = list1;
    ListNode* l2 = list2;
    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            if (!plist)
            {
                plist = ptail = l1;
            }
            else
            {
                ptail->next = l1;
                ptail = ptail->next;
            }
            l1 = l1->next;
        }
        else
        {
            if (!plist)
            {
                plist = ptail = l2;
            }
            else
            {
                ptail->next = l2;
                ptail = ptail->next;
            }
            l2 = l2->next;
        }

    }
    if (l1)
    {
        if (!plist)
        {
            plist = ptail = l1;
        }
        else
        {
            ptail->next = l1;
        }
    }
    if (l2)
    {
        if (!plist)
        {
            plist = ptail = l2;
        }
        else
        {
            ptail->next = l2;
        }
    }
    return plist;
}



int main()
{
    ListNode* node1 = bunode(1);
    ListNode* node2 = bunode(2);
    ListNode* node3 = bunode(3);
    ListNode* node4 = bunode(4);
    ListNode* node5 = bunode(5);
    ListNode* node6 = bunode(6);
    ListNode* node7 = bunode(7);
    ListNode* node8 = bunode(8);

    node1->next = node3;
    node3->next = node5;
    node5->next = node7;

    node2->next = node4;
    node4->next = node6;
    node6->next = node8;
    mergeTwoLists(node1, node2);

    return 0;
}